package net.projecteuler.prob;

import java.util.Arrays;

import net.projecteuler.util.DigitUtil;
import net.projecteuler.util.FactorUtil;

public class Problem70 implements Runnable {

	private static final int MAX = 10000000; // 10^7
	
	@Override
	public void run() {
		double ratioMin = 1000.0;
		
		for(int i = 2; i < MAX; i++){
			if(i % 2 == 0 || i % 3 == 0 || i % 5 == 0 || i % 7 == 0 || i % 11 == 0 || i % 13 == 0 || i % 17 == 0
					 || i % 19 == 0 || i % 23 == 0 || i % 29 == 0 || i % 31 == 0 || i % 37 == 0 || i % 41 == 0) continue;
			
			int totient = FactorUtil.totientPhi(i);
			int[] digit = DigitUtil.digits(i);
			int[] digit2 = DigitUtil.digits(totient);
			
			if(digit.length != digit2.length) continue;

			Arrays.sort(digit);
			Arrays.sort(digit2);
			
			boolean valid = true;
			for(int j = 0; j < digit.length; j++)
				if(digit[j] != digit2[j]){
					valid = false;
					break;
				}
			
			if(!valid) continue;
					
			double ratio = (double)i / (double)totient;
			if(ratio < ratioMin){
				ratioMin = ratio;
				System.out.println(i + "->" + totient + " : " + ratioMin);
			}
		}
	}

}
